window.onload = function () {
  /**
   * 70. 爬楼梯
   */
  console.log(climbStairs(2))

  /**
   * 433. 最小基因变化
   */
  console.log(minMutation("AACCGGTT", "AACCGGTA", ["AACCGGTA"]))

  /**
   * 51. N 皇后
   */
  console.log(solveNQueens(4))
}

/**
 * 70. 爬楼梯
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
  let p = 0, q = 0, r = 1;
  for (let i = 1; i <= n; ++i) {
    p = q;
    q = r;
    r = p + q;
  }
  return r;
};

/**
 * 433. 最小基因变化
 * @param {string} start
 * @param {string} end
 * @param {string[]} bank
 * @return {number}
 */
var minMutation = function (start, end, bank) {
  let bankSet = new Set(bank);
  if (!bankSet.has(end)) return -1;
  let queue = [[start, 0]];
  let dna = ["A", "C", "G", "T"];
  while (queue.length) {
    let [node, count] = queue.shift();
    if (node === end) return count;
    for (let i = 0; i < node.length; i++) {
      for (let j = 0; j < dna.length; j++) {
        let d = node.slice(0, i) + dna[j] + node.slice(i + 1);
        if (bankSet.has(d)) {
          queue.push([d, count + 1]);
          bankSet.delete(d);
        }
      }
    }
  }
  return -1;
};

/**
 * 51. N 皇后
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = (n) => {
  const board = new Array(n);
  for (let i = 0; i < n; i++) {
    board[i] = new Array(n).fill('.');
  }

  const cols = new Set();  // 列集，记录出现过皇后的列
  const diag1 = new Set(); // 正对角线集
  const diag2 = new Set(); // 反对角线集
  const res = [];

  const helper = (row) => {
    if (row == n) {
      const stringsBoard = board.slice();
      for (let i = 0; i < n; i++) {
        stringsBoard[i] = stringsBoard[i].join('');
      }
      res.push(stringsBoard);
      return;
    }
    for (let col = 0; col < n; col++) {
      // 如果当前点的所在的列，所在的对角线都没有皇后，即可选择，否则，跳过
      if (!cols.has(col) && !diag1.has(row + col) && !diag2.has(row - col)) {
        board[row][col] = 'Q';  // 放置皇后
        cols.add(col);          // 记录放了皇后的列
        diag2.add(row - col);   // 记录放了皇后的正对角线
        diag1.add(row + col);   // 记录放了皇后的负对角线
        helper(row + 1);
        board[row][col] = '.';  // 撤销该点的皇后
        cols.delete(col);       // 对应的记录也删一下
        diag2.delete(row - col);
        diag1.delete(row + col);
      }
    }
  };
  helper(0);
  return res;
};


